class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution01 {
	private int maxSum = Integer.MIN_VALUE;
	
    public int maxPathSum(TreeNode root) {
		int sigleSum = dfs(root);
		return Math.max(maxSum, sigleSum);
    }

	/** 后续遍历 */
	private int dfs(TreeNode root){
		if(root == null){
			return 0;
		}

		int leftMax = Math.max(0, dfs(root.left));
		int rightMax = Math.max(0, dfs(root.right));
		// 左 + 根 + 右
		maxSum = Math.max(maxSum, root.val + leftMax + rightMax);

		// 根+左子树 或 根+右子树
		return root.val + Math.max(leftMax, rightMax);
	}
}
